package bin_tree;

import java.util.NoSuchElementException;

/**
 * @author shkstart
 * 基于Int的二分搜索树，不包含重复节点
 * @create 2022-11-02-21:59
 */
public class BST {

    //    节点个数
    private int size;
    //    根节点
    private Node root;


    //    BST 的节点定义
    private class Node {

        private int val;
        private Node left;
        private Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    public void add(int value) {
        root = add(root, value);
    }

    private Node add(Node root, int value) {
//        当root为空时，走到叶子节点，添加新元素
        if (root == null) {
            root = new Node(value);
            size++;
            return root;
        }
        if (value < root.val) {
//            添加到左子树
            root.left = add(root.left, value);
            return root;
        } else {
//            添加到右子树
            root.right = add(root.right, value);
            return root;
        }

    }

    //    查找
    public boolean contains(int val) {
        return contains(root, val);
    }

    private boolean contains(Node root, int val) {
        if (root == null) {
            return false;
        }
//        根节点恰好就是带查找节点
        else if (root.val == val) return true;
//        在左子树中找
        else if (root.val > val) return contains(root.left, val);
//        在右子树中查找
        return contains(root.right, val);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root, 0, sb);

        return sb.toString();
    }

    //    寻找最大数
    public int maximum() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty");
        }
        Node maxNode = maximum(root);
        return maxNode.val;
    }

    private Node maximum(Node root) {
        if (root.right == null) {
//            右孩子为空
            return root;
        }
        return maximum(root.right);
    }

    //    寻找最小数
    public int minimum() {
        if (size == 0) {
            throw new NoSuchElementException("bst is empty");
        }
        Node minNode = minimum(root);
        return minNode.val;
    }

    private Node minimum(Node root) {
        if (root.left == null) {
            return root;
        }
        return minimum(root.left);
    }

    //    删除最小值节点并返回值
    public int removeMin() {
        int val = minimum();
        root = removeMin(root);
        return val;
    }

    //    删除以root为根节点的BST中的最小值节点，返回删除后的根节点
    private Node removeMin(Node root) {
        if (root.left == null) {
//            此时找到最小值节点，将右树返回
            Node right = root.right;
//        将右树置空， 相当于node.nextnull
            root.right = null;
            size--;
            return right;
        }
        root.left = removeMin(root.left);
        return root;
    }

    //    删除最大值并返回节点
    public int removeMax() {
        int val = maximum();
        root = removeMax(root);
        return val;
    }

    private Node removeMax(Node root) {
        if (root.right == null) {
            Node left = root.left;
            root.left = null;
            size--;
            return left;
        }
        root.right = removeMax(root.right);
        return root;

    }

    //    按任意值删除
    public void remove(int val) {
        root = remove(root, val);
    }

    //    在以root为根节点的二叉树中删除值为val的节点
//    返回删除后的根节点
    private Node remove(Node root, int val) {
        if (root == null) {
            return null;
        } else if (val < root.val) {
//            在左树种寻找删除
            root.left = remove(root.left, val);
            return root;

        } else if (val > root.val) {
//            此时在右树删除
            root.right = remove(root.right, val);
            return root;
        } else {
//            此时root就是待删除的节点
            if (root.left == null) {
//                没有左树，只有右树  返回右树即可
                Node right = root.right;
                root.right = null;
                size--;
                return right;
            }
            if (root.right == null) {
//                没有右树，只有左树 返回左树即可
                Node left = root.left;
                root.left = null;
                size--;
                return left;
            }
//                此时左右孩子都不为空,需要找到该节点的后继节点
            Node successor = minimum(root.right);
//                在右子树中删除最小值,链接为successor的右子树
//                删除右子树中的最小值,并且返回树根
            successor.right = removeMin(root.right);
//                连接root的左子树为后继successor的左子树
            successor.left = root.left;
            root.left = root.right = null;
            return successor;


        }


    }


    /*
    先序遍历二分搜索树
    BST的根节点
    当前树的深度
     */
    private void generateBSTString(Node root, int depth, StringBuilder sb) {

        if (root == null) {
            sb.append(generateBSTDepth(depth)).append("Null\n");
            return;
        }
        //先访问根节点
        sb.append(generateBSTDepth(depth)).append(root.val).append("\n");
//        递归左子树
        generateBSTString(root.left, depth + 1, sb);
        //        递归右子树
        generateBSTString(root.right, depth + 1, sb);

    }

    private String generateBSTDepth(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}



